import math
import random

def assign_cluster(x, c):
    distances = []
    for center in c:
        dist = math.sqrt(sum((x[i] - center[i])**2 for i in range(len(x))))
        distances.append(dist)
    return distances.index(min(distances))

def Kmeans(data, k, epsilon=1e-4, iteration=100):
    if not data or k <= 0 or k > len(data):
        raise ValueError("Invalid input parameters")
    
    n_features = len(data[0])
    centroids = random.sample(data, k)
    
    for iter_count in range(iteration):
        clusters = {i: [] for i in range(k)}
        for point in data:
            cluster_idx = assign_cluster(point, centroids)
            clusters[cluster_idx].append(point)
        
        new_centroids = []
        for i in range(k):
            if clusters[i]:
                centroid = []
                for j in range(n_features):
                    dim_sum = sum(point[j] for point in clusters[i])
                    centroid.append(dim_sum / len(clusters[i]))
                new_centroids.append(centroid)
            else:
                new_centroids.append(centroids[i])
        
        max_change = 0
        for i in range(k):
            change = math.sqrt(sum((centroids[i][j] - new_centroids[i][j])**2 for j in range(n_features)))
            max_change = max(max_change, change)
        
        centroids = new_centroids
        
        if max_change < epsilon:
            print(f"Converged after {iter_count + 1} iterations")
            break
    
    return clusters, centroids

if __name__ == "__main__":
    random.seed(42)
    sample_data = []
    for center in [[2, 2], [8, 8], [8, 2]]:
        for _ in range(10):
            sample_data.append([
                center[0] + random.gauss(0, 1.5),
                center[1] + random.gauss(0, 1.5)
            ])
    
    clusters, centroids = Kmeans(sample_data, k=3, epsilon=1e-4, iteration=100)
    
    print("聚类中心:")
    for i, centroid in enumerate(centroids):
        print(f"聚类 {i}: ({centroid[0]:.2f}, {centroid[1]:.2f})")
    
    print("\n聚类结果:")
    for cluster_idx, points in clusters.items():
        print(f"聚类 {cluster_idx}: {len(points)} 个点")
        for point in points:
            print(f"  ({point[0]:.2f}, {point[1]:.2f})")